#ifndef __LINKLIST_H_
#define __LINKLIST_H_

#include <stddef.h>
#include "DynamicArray.h"
using ElementType = int;

class LinkList
{
public:
    LinkList();
    LinkList(const LinkList& list);
    LinkList& operator=(const LinkList& list);
    ~LinkList();


    //插入
    //尾插法
    void InsertTail(const ElementType& element);
    //头插法
    void InsertHead(const ElementType& element);
    //中间插
    void InsertByIndex(size_t index, const ElementType& element);

    //删除
    //按位置删除
    void RemoveByIndex(size_t index);
    //按值删除
    void RemoveByElement(const ElementType& element);

    //按位置查找
    ElementType* FindByIndex(size_t index);
    //按值查找
    DARRAY::DynamicArray FindByElement(const ElementType& element);

    //修改
    //按位置修改
    void UpdateByIndex(size_t index, const ElementType& element);
    //按值修改
    void UpdateByElement(const ElementType& oldValue, const ElementType& newValue);

    //排序
    void BubbleSort();
    void Sort();

    //倒数第n个元素
    ElementType* GetReserveIndex(size_t index);

    //归并
    LinkList Merge(const LinkList& list);
    //交并补
    //取交集
    LinkList FindInsertSection(const LinkList &list);
    //取并集
    LinkList FindUnionSection(const LinkList &list);
    //取补集
    LinkList FindDifference(const LinkList &list);

    //链表逆序
    void Reserve();

    void Reserve2();
    void show();
private:
    struct Node
    {
        Node(const ElementType& value)
        {
            this->value = value;
            next = nullptr;
        }
        ElementType value;  //数据域
        Node *next;  //指针域
    };
    void FastSort(Node *start, Node *end);
    Node *reserve(Node *node);
    Node *head;  //头指针
    size_t size;  //元素的个数
};



#endif